{ "cells": [ { "cell_type": "markdown", "source": [ "# Mixed Integer Programming with PuLP\n", "\n", "## Try me\n", "[![Open In Colab](../../_static/colabs_badge.png)](https://colab.research.google.com/github/ffraile/operations-research-notebooks/blob/main/docs/source/MIP/tutorials/PuLP%20and%20Python%20MIP%20Tutorial.ipynb)[![Binder](../../_static/binder_badge.png)](https://mybinder.org/v2/gh/ffraile/operations-research-notebooks/main?labpath=docs%2Fsource%2FMIP%2Ftutorials%2FPuLP%20and%20Python%20MIP%20Tutorial.ipynb)\n", "\n", "## Introduction\n", "This tutorial shows how to program and solve Mixed Integer Programming (MIP) problems in Python using the PuLP library.\n", "\n", "This tutorial builds upon the tutorial on PuLP we saw in the previous unit:\n", "\n", "[Continuous Linear Programming with PuLP](../../CLP/libraries/Python%20PuLP%20Tutorial.ipynb)\n", "\n", "## Requirements\n", "To run this tutorial you will need to install PuLP, following the guides in the previous tutorial. For instance, if you are using this tutorial in Colabs, run the following cell to install PuLP:\n", "\n", "\n" ], "metadata": { "collapsed": false } }, { "cell_type": "code", "execution_count": null, "outputs": [], "source": [ "# Install PuLP\n", "!pip install pulp" ], "metadata": { "collapsed": false } }, { "cell_type": "markdown", "source": [ "## Example\n", "We will use the [Allocating order to machines](../exercises/Allocating%20Orders%20to%20Machines.ipynb) problem to guide the tutorial. For convenience, this is the mathematical formulation:\n", "\n", "### indices\n", "- **i**: index to identify each machine (resource element) $i \\in \\{1,2,3,4,5\\}$\n", "- **j**: index to identify each production order (task element) $j \\in \\{1,2,3,4,5\\}$\n", "\n", "### Coefficients\n", "$C = \\begin{bmatrix}\n", "c_{11} & c_{12} & \\cdots & c_{1n} \\\\\n", "c_{21} & c_{22} & \\cdots & c_{2n} \\\\\n", "\\vdots & \\vdots & \\ddots & \\vdots \\\\\n", "c_{m1} & c_{m2} & \\cdots & c_{mn} \\\\\n", "\\end{bmatrix}\n", "= \\begin{bmatrix}\n", "16 & 2 & 8 & 3 & 3 \\\\\n", "4 & 14 & 10 & 7 & 6 \\\\\n", "9 & 7 & 3 & 6 & 8 \\\\\n", "5 & 5 & 12 & 10 & 11 \\\\\n", "6 & 13 & 11 & 5 & 7 \\\\\n", "\\end{bmatrix}$\n", "\n", "### Objective function\n", "\n", "$\\min z = \\sum_i\\sum_j{x_{ij}*c_{ij}}$\n", "\n", "### Constraints\n", "\n", "$\\sum_j{x_{ij}} \\leq 1 \\quad \\forall i$\n", "\n", "$\\sum_i{x_{ij}} \\leq 1 \\quad \\forall j$\n", "\n" ], "metadata": { "collapsed": false } }, { "cell_type": "markdown", "source": [ "## Solution in Python\n", "The following script models and solves the problem using PuLP:\n" ], "metadata": { "collapsed": false } }, { "cell_type": "code", "execution_count": 2, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Status: Optimal\n", "Objective value: 20.0\n", "x_(1,_1) = 0.0\n", "x_(1,_2) = 0.0\n", "x_(1,_3) = 0.0\n", "x_(1,_4) = 0.0\n", "x_(1,_5) = 1.0\n", "x_(2,_1) = 1.0\n", "x_(2,_2) = 0.0\n", "x_(2,_3) = 0.0\n", "x_(2,_4) = 0.0\n", "x_(2,_5) = 0.0\n", "x_(3,_1) = 0.0\n", "x_(3,_2) = 0.0\n", "x_(3,_3) = 1.0\n", "x_(3,_4) = 0.0\n", "x_(3,_5) = 0.0\n", "x_(4,_1) = 0.0\n", "x_(4,_2) = 1.0\n", "x_(4,_3) = 0.0\n", "x_(4,_4) = 0.0\n", "x_(4,_5) = 0.0\n", "x_(5,_1) = 0.0\n", "x_(5,_2) = 0.0\n", "x_(5,_3) = 0.0\n", "x_(5,_4) = 1.0\n", "x_(5,_5) = 0.0\n" ] }, { "name": "stderr", "output_type": "stream", "text": [ "C:\\Users\\franc\\PycharmProjects\\operations-research-notebooks\\venv\\Lib\\site-packages\\pulp\\pulp.py:1316: UserWarning: Spaces are not permitted in the name. Converted to '_'\n", " warnings.warn(\"Spaces are not permitted in the name. Converted to '_'\")\n" ] } ], "source": [ "# Import PuLP modeler functions\n", "import pulp\n", "\n", "# Create the model\n", "model = pulp.LpProblem(name=\"Allocating orders to machines\", sense=pulp.LpMinimize)\n", "\n", "# Define indices\n", "machines = [1, 2, 3, 4, 5]\n", "orders = [1, 2, 3, 4, 5]\n", "\n", "# Define decision variables\n", "x = pulp.LpVariable.dicts(\"x\",\n", " [(i,j) for i in machines for j in orders],\n", " cat=pulp.LpBinary,\n", " )\n", "\n", "# Define coefficient matrix\n", "C = [[16, 2, 8, 3, 3],\n", " [4, 14, 10, 7, 6],\n", " [9, 7, 3, 6, 8],\n", " [5, 5, 12, 10, 11],\n", " [6, 13, 11, 5, 7]]\n", "\n", "# Define objective function\n", "model += pulp.lpSum([C[i][j]*x[(i+1,j+1)] for i in range(len(machines)) for j in range(len(orders))])\n", "\n", "# Define constraints\n", "for i in machines:\n", " model += pulp.lpSum([x[(i,j)] for j in orders]) == 1\n", "\n", "for j in orders:\n", " model += pulp.lpSum([x[(i,j)] for i in machines]) == 1\n", "\n", "# Solve the problem\n", "model.solve()\n", "\n", "# Print the status of the solution\n", "print(\"Status:\", pulp.LpStatus[model.status])\n", "\n", "# Print the value of the objective function\n", "print(\"Objective value:\", pulp.value(model.objective))\n", "\n", "# Print the value of the decision variables\n", "for v in model.variables():\n", " print(v.name, \"=\", v.varValue)\n" ], "metadata": { "collapsed": false } }, { "cell_type": "markdown", "source": [ "### Code Explanation\n", "The code is very similar to the efficient code we used in the previous tutorial. The only difference is in the way we define the decision variables. Let's see the differences:\n", "\n", "#### Decision variables\n", "We use the same function ```pulp.LpVariable.dicts``` to define the decision variables. There are two main differences:\n", "- **Definition or integer or binary decision variables: ** We use the parameter ```cat=pulp.LpBinary``` to define the decision variables as binary. If we wanted to define them as integer, we would use ```cat=pulp.LpInteger```.\n", "- **Definition of the indices: ** We use a list comprehension to define the indices of the decision variables. The list comprehension is a very powerful tool in Python that allows us to define lists in a very compact way. The list comprehension we use is the following:\n", "\n", "```python\n", "[(i,j) for i in machines for j in orders]\n", "```\n", "\n", "This list comprehension defines a list of tuples, where each tuple is defined as ```(i,j)```, where ```i``` takes the values in the list ```machines``` and ```j``` takes the values in the list ```orders```. This way we define all the possible combinations of ```i``` and ```j``` in a very compact way.\n", "\n", "Thus, the code:\n", "\n", "```python\n", "x = pulp.LpVariable.dicts(\"x\",\n", " [(i,j) for i in machines for j in orders],\n", " cat=pulp.LpBinary,\n", " )\n", "```\n", "\n", "Defines a total of 5x5 = 25 decision variables, one for each combination of ```i``` and ```j```. The decision variables can be accessed using a tuple. For instance, ```x[(1,1)]``` is the decision variable associated with the combination ```i=1``` and ```j=1```.\n", "\n", "### Reading data from an Excel file\n", "In the previous tutorial, we defined the coefficient matrix in the code. However, in real problems, the data is normally stored in a file. In this case, we will use an Excel file to store the data. We will see how to read the data from the Excel file and store it in a ```DataFrame```. Then, we will see how to access the data in the ```DataFrame``` to define the coefficient matrix. The following code shows how to load the data from an Excel file named ```costs.xlsx```:\n", "\n", "\n" ], "metadata": { "collapsed": false } }, { "cell_type": "code", "execution_count": null, "outputs": [], "source": [ "import pandas as pd\n", "import pulp\n", "from IPython.display import display\n", "\n", "# import the data from the Excel file\n", "dataset_df = pd.read_excel(\"costs.xlsx\", index_col=[0,1])\n", "c = dataset_df['cost']\n", "\n", "# Pivot the data to show it in a more convenient way\n", "dataset_df = dataset_df.reset_index()\n", "dataset_df = dataset_df.pivot(index='machine', columns='order', values='cost')\n", "display(dataset_df)\n", "\n", "# Create the model\n", "model = pulp.LpProblem(name=\"Allocating orders to machines\", sense=pulp.LpMinimize)\n", "\n", "# Define indices\n", "machines = [1, 2, 3, 4, 5]\n", "orders = [1, 2, 3, 4, 5]\n", "\n", "# Define decision variables\n", "x = pulp.LpVariable.dicts(\"x\",\n", " [(i,j) for i in machines for j in orders],\n", " cat=pulp.LpBinary,\n", " )\n", "\n", "# Define objective function\n", "\n", "model += pulp.lpSum([c[i][j]*x[(i,j)] for i in machines for j in orders])\n", "\n", "# Define constraints\n", "for i in machines:\n", " model += pulp.lpSum([x[(i,j)] for j in orders]) == 1\n", "\n", "for j in orders:\n", " model += pulp.lpSum([x[(i,j)] for i in machines]) == 1\n", "\n", "# Solve the problem\n", "model.solve()\n", "\n", "# Print the status of the solution\n", "print(\"Status:\", pulp.LpStatus[model.status])\n", "\n", "\n", "# Create a dataframe to store the solutions\n", "x_df = pd.DataFrame.from_dict(x, orient=\"index\", dtype=object, columns=[\"variable_object\"])\n", "\n", "# Extract the values of the decision variables from the solution\n", "x_df[\"solution_value\"] = x_df[\"variable_object\"].apply(lambda item: item.varValue)\n", "\n", "# Drop the pulp decision variables\n", "x_df = x_df.drop(columns=[\"variable_object\"])\n", "\n", "# Pivot the dataframe to show the solution in a more convenient way\n", "x_df = x_df.reset_index()\n", "\n", "x_df['machine'] = x_df['index'].apply(lambda i: i[0])\n", "x_df['order'] = x_df['index'].apply(lambda i: i[1])\n", "\n", "# Drop the index column\n", "x_df = x_df.drop(columns=[\"index\"])\n", "\n", "# Reorder the columns to show the solution in a more intuitive way\n", "x_df = x_df[[\"machine\", \"order\", \"solution_value\"]]\n", "\n", "# Pivot the dataframe to show the solution in a more convenient way\n", "x_df = x_df.pivot(index='machine', columns='order', values='solution_value')\n", "display(x_df)\n", "\n", "# Safe to an Excel file\n", "with pd.ExcelWriter('solution.xlsx') as writer:\n", " x_df.to_excel(writer, sheet_name=\"X\")\n" ], "metadata": { "collapsed": false } }, { "cell_type": "markdown", "source": [ "The following sections explain the code in detail.\n", "\n", "### Code Explanation\n", "#### Preparing the dataset\n", "Normally, the data for our problem is going to be stored in tabular format in file formats like Excel. In this case, we can use the ```pandas``` library to read the data from the Excel file and store it in a ```DataFrame```. Then, we can use the ```DataFrame``` to access the data in a very convenient way. First, just copy the following table in an Excel file:\n", "```tsv\n", "machine\torder\tcost\n", "1\t1\t16\n", "1\t2\t2\n", "1\t3\t8\n", "1\t4\t3\n", "1\t5\t3\n", "2\t1\t4\n", "2\t2\t14\n", "2\t3\t10\n", "2\t4\t7\n", "2\t5\t6\n", "3\t1\t9\n", "3\t2\t7\n", "3\t3\t3\n", "3\t4\t6\n", "3\t5\t8\n", "4\t1\t5\n", "4\t2\t5\n", "4\t3\t12\n", "4\t4\t10\n", "4\t5\t11\n", "5\t1\t6\n", "5\t2\t13\n", "5\t3\t11\n", "5\t4\t5\n", "5\t5\t7\n", "```\n", "\n", "Make sure you paste the table in the first sheet of the Excel file as **text**. It should look like this:\n", "\n", "![Excel file](img/assignment_dataset.png)\n", "\n", "> Important! If you notice that all the text of a raw is in the same sure, try to Past As text from the Edit menu in Excel.\n", "\n", "Name the file ```costs.xlsx```.\n", "\n", "\n", "\n", "#### Uploading the dataset to your Python environment\n", "Now, you need to make sure that the Excel file is in the working directory of your Python environment. If you are using Colabs, you can use the file menu to upload it as shown in this tutorial:\n", "\n", "[Working with files](https://programming.engineeringcodehub.com/en/latest/Data%20Manipulation/tutorials/Files.html)\n", "\n", "#### Loading the dataset in a DataFrame\n", "Now, we can use the ```pandas``` library to load the data in a ```DataFrame```:\n", "\n", "```python\n", "import pandas as pd\n", "dataset_df = pd.read_excel(\"costs.xlsx\", index_col=[0,1])\n", "c = dataset_df['cost']\n", "```\n", "\n", "The ```index_col``` parameter indicates that the first two columns of the Excel file are the indices of the ```DataFrame```.\n", "\n", "#### Accessing the data in the DataFrame\n", "Note that we have stored the costs in a variable named ```c```. This is because we will use the ```DataFrame``` to access the data in a very convenient way. For instance, if we want to access the cost of machine 1 and order 1, we can use the following code:\n", "\n", "```python\n", "print(c[1,1])\n", "```\n", "\n", "This will print the value of the cell in the first row and first column of the ```DataFrame```, corresponding to machine 1 and production order 1.\n", "\n", "#### Pivoting the DataFrame to show the data in a more convenient way\n", "To show the data in a more convenient way, we can pivot the ```DataFrame```:\n", "\n", "```python\n", "dataset_df = dataset_df.reset_index()\n", "dataset_df = dataset_df.pivot(index='machine', columns='order', values='cost')\n", "display(dataset_df)\n", "```\n", "\n", "This will show the data in a very convenient way, environments like Colabs provide interactive widgets to further work with the data.\n", "\n", "#### Defining the objective function\n", "Now, we can modify the objective function slightly to access the data in the ```DataFrame```:\n", "\n", "```python\n", "model += pulp.lpSum([c[i][j]*x[(i,j)] for i in machines for j in orders])\n", "```\n", "\n", "Note that since the indices of c are the same as the indices of the decision variables, the code is very compact and close to mathematical notation.\n", "\n", "#### Exporting to Excel\n", "Finally, we can put the variables in a dataframe:\n", "\n", "```python\n", "# Create a dataframe to store the solutions\n", "x_df = pd.DataFrame.from_dict(x, orient=\"index\", dtype=object, columns=[\"variable_object\"])\n", "\n", "# Extract the values of the decision variables from the solution\n", "x_df[\"solution_value\"] = x_df[\"variable_object\"].apply(lambda item: item.varValue)\n", "```\n", "\n", "This code first creates a dataframe with the decision variables and then extracts the values of the decision variables using a lambda function. Pandas will apply the lambda function to each row of the dataframe, passing the decision variable object as a parameter. The lambda function will return the value of the decision variable.\n", "\n", "Finally, we can pivot the dataframe and export it to excel using the following code:\n", "\n", "\n", "```python\n", "with pd.ExcelWriter('solution.xlsx') as writer:\n", " x_df.to_excel(writer, sheet_name=\"X\")\n", "```\n", "\n", "This code will create an Excel file named ```solution.xlsx``` with a sheet named ```X``` containing the solution.\n", "If our problem has more decision variables, we can create more sheets and store the solutions in different sheets.\n", "\n" ], "metadata": { "collapsed": false } }, { "cell_type": "markdown", "source": [ "## Analysis Questions\n", "1. Analyse the solution and explain the assignment of orders to machines that the model has found in your own words.\n", "2. How would you modify the model to allow for the assignment of more than one order to each machine?\n", "3. Use an AI assistant to obtain a Python script to solve the problem using PuLP. Compare the script with the one we have developed in this tutorial. What are the main differences?\n", "4. Ask an AI assistant to provide a greedy algorithm to solve the problem in Python. Try the algorithm. Does the algorithm provide an optimal solution? Why?\n", "5. Try to solve different instances of the problem, for instance adding more machines or more production orders. What changes are needed in the script. How can you make the script more scalable?" ], "metadata": { "collapsed": false } } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.6" } }, "nbformat": 4, "nbformat_minor": 0 }